#include<iostream>

#define IFLINK 0


template<class T>
class Node
{
public:
    T val;
    Node* next = nullptr;

public:
    Node(void) : val(0), next(nullptr){}
    Node(T value) : val(value), next(nullptr){}
    ~Node(){}
};

template<class T>
class Queue
{
public:
    Node<T>* front;
    Node<T>* rear; 
    int size;


public:
    Queue(void)
    {
        this->front = new Node<T>(0);
        this->rear = front;
        this->size = 0;
    }

    void pushQueue(T value)
    {
        if(size == 0)
        {
            rear = front;
        }
        Node<T>* newnode = new Node<T>(value);
        rear->next = newnode;
        rear = rear->next;
        size++;
    }

    void popQueue(void)
    {
        if(size == 0)
        {
            printf("The queue has no element\n");
            return ;
        }
        Node<T>* tmp = front->next;
        front->next = tmp->next;
        delete tmp;
        tmp = nullptr;
        size--;
    }

    void printQueue(void)
    {
        Node<T>* p = front->next;
        std::cout << "front ";
        while(p!=nullptr)
        {
            std::cout << p->val <<" ";
            p = p->next;
        }
        std::cout <<"rear"<< std::endl;
    }


    ~Queue()
    {
        Node<T>* tmp = nullptr;
        while(size!=0)
        {
            tmp = front->next;
            front->next = tmp->next;
            delete tmp;
            size--;
        }

        delete front;
        front = nullptr;

    }
};


// 循环队列
template<class T>
class arryQueue
{
public:
    int n = 10;
    T queue[10] = {};
    int front=0, rear=0;
    int size = 0;

public:
    arryQueue(void) : size(0), front(0), rear(0){}
    ~arryQueue(void){}

    void pushQueue(int val)
    {
        if((rear+1)%n == front) // 满队
        {
            printf("The queue is full\n");
        }
        else
        {
            queue[rear] = val;
            rear = (rear+1)%n;
            size++;
        }
    }

    void popQueue(void)
    {
        if(rear == front)
        {
            printf("The queue has no elements\n");
        }
        else
        {
            rear = (rear+n-1)%n;
            size--;
        }
    }

    void printQueue(void)
    {
        int tmp = front;
        std::cout << "front ";
        while(tmp!=rear)
        {
            std::cout << this->queue[tmp] <<" ";
            tmp = (tmp+1)%n;
        }
        std::cout <<"rear"<< std::endl;
    }



};


#if IFLINK

int main()
{


    int num[10] = {1, 2, 3, 4,5,6,7,8,9,10};
    Queue<int>* q = new Queue<int>();
    int length = sizeof(num)/sizeof(num[0]);
    for(int i=0; i<length; i++)
    {
        q->pushQueue(num[i]);
    }

    q->printQueue();

    q->popQueue();
    q->popQueue();
    q->popQueue();
    q->popQueue();
    q->printQueue();

    q->popQueue();
    q->popQueue();
    q->popQueue();
    q->popQueue();
    q->popQueue();
    q->popQueue();
    q->printQueue();

    q->popQueue();
    q->pushQueue(100);
    q->pushQueue(200);
    q->pushQueue(300);
    q->pushQueue(400);
    q->printQueue();
    delete q;

    return 0;
}

#else



int main()
{


    int num[10] = {1, 2, 3, 4,5,6,7,8,9,10};
    arryQueue<int>* q = new arryQueue<int>();
    int length = sizeof(num)/sizeof(num[0]);
    for(int i=0; i<length; i++)
    {
        q->pushQueue(num[i]);
    }

    q->printQueue();

    q->popQueue();
    q->popQueue();
    q->popQueue();
    q->popQueue();
    q->printQueue();

    q->popQueue();
    q->popQueue();
    q->popQueue();
    q->popQueue();
    q->popQueue();
    q->popQueue();
    q->printQueue();

    q->popQueue();
    q->pushQueue(100);
    q->pushQueue(200);
    q->pushQueue(300);
    q->pushQueue(400);
    q->printQueue();
    delete q;

    return 0;
}





#endif